#include <queue>
#include <unordered_map>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

class Solution
{
public:
    string alienOrder(vector<string>& words)
    {
        string rs;
        unordered_map<char, unordered_set<char>> edges;
        unordered_map<char, int> in;
        int n = words.size();

        for(int i=0; i<n; i++)
        {
            int m = words[i].size();
            for(int j=0; j<m; j++)
            {
                in[words[i][j]] = 0;
            }
        }

        for(int i=0; i<n; i++)
        {
            for(int j=i+1; j<n; j++)
            {
                int l = min(words[i].size(), words[j].size());
                int p = 0;//因为下面的特判得定义到for外
                for(p=0; p<l; p++)
                {
                    if(words[i][p] != words[j][p])
                    {
                        char a = words[i][p], b = words[j][p];
                        if(!edges.count(a) || !edges[a].count(b))//字母a不在hash中，或b不在a的hash中
                        {
                            edges[a].insert(b);
                            in[b]++;
                        }
                        break;
                    }
                }
                //特判不合法情况
                if(p == words[j].size() && p < words[i].size())     return "";
            }
        }

        queue<char> q;
        for(auto& [a,b] : in)
        {
            if(b == 0)
            {
                q.emplace(a);
                rs += a;
            }
        }

        while(!q.empty())
        {
            auto tmp = q.front();
            q.pop();
            for(char ch : edges[tmp])
            {
                if(--in[ch]==0)
                {
                    q.emplace(ch);
                    rs += ch;
                }
            }
        }

        for(auto& [a,b] : in)
        {
            if(b)
                return "";
        }
        return rs;
    }
};